package com.rui.study.algorithm.P_序列化和反序列化二叉搜索树;

import com.rui.study.algorithm.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-23 09:09
 **/
public class Solution_未完成 {

    // TODO
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuffer buf = new StringBuffer("[");
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return "";
        }
        queue.push(root);
        TreeNode lastValid = root;
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.pop();
            if (tmp != null) {
                buf.append(tmp.val + ", ");
                lastValid = tmp.right != null ? tmp.right : tmp.left != null ? tmp.left : lastValid;
                if (tmp == lastValid) {
                    break;
                }
                queue.addLast(tmp.left);
                queue.addLast(tmp.right);
            } else {
                queue.addLast(null);
                queue.addLast(null);
                buf.append("null, ");
            }
        }
        buf.delete(buf.lastIndexOf(","), buf.length() - 1);
        buf.append("]");
        String result = buf.toString();
//        result = result.replaceAll("[null,]+\\]$", "]");
        return result;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String encoded) {
        if (encoded == null || !encoded.matches("^\\[(.+)\\]$")) {
            return null;
        }
        String data = "";
        Matcher matcher = Pattern.compile("^\\[(.+)\\]$").matcher(encoded);
        if (matcher.find()) {
            data = matcher.group(1);
        }
        String[] vals = data.split(",");
        System.out.println(Arrays.toString(vals));

        TreeNode[] nodes = new TreeNode[vals.length];
        for (int i = 0; i < vals.length; i++) {
            if ("null".equals(vals[i])) {
                continue;
            }
            nodes[i] = new TreeNode(Integer.valueOf(vals[i]));
        }

        for (int i = 0; i < nodes.length / 2; i++) {
            if (nodes[i] == null) {
                continue;
            }
            nodes[i].left = nodes[2 * i + 1];
            if (2 * i + 2 < nodes.length) {
                nodes[i].right = nodes[2 * i + 2];
            }
        }

        return nodes[0];
    }


    public static void main(String[] args) {

        // 构建二叉搜索树
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        TreeNode root = node5;
        root.left = node3;
        root.right = node6;
        node3.left = node2;
        node3.right = node4;
        node6.right = node7;


        long startD = System.currentTimeMillis();
        Solution_未完成 solution = new Solution_未完成();
//        TreeNode result = solution.deserialize(null);
//        TreeNode result = solution.deserialize("");
//        TreeNode result = solution.deserialize("");
//        TreeNode result = solution.deserialize("[]");
//        TreeNode result = solution.deserialize("[1]");
//        TreeNode result = solution.deserialize("[3,2,4,1]");
//        TreeNode result = solution.deserialize("[5,3,6,2,4,null,7]");
//        TreeNode result = solution.deserialize("[1,null,2]");
//        TreeNode result = solution.deserialize("[1,null,2,null,null,null,3]");
//        TreeNode result = solution.deserialize("[50,20,60,10,30,56,80,5,15,25,40,52,59,70,90,3,8,12,18]");
        TreeNode result = solution.deserialize("[46,7,48,5,36,47,49,1,6,12,39,null,null,null,null,0,2,null,null,10,30,37,45,null,null,null,3,9,11,15,32,null,38,40,null,null,4,8,null,null,null,13,19,31,35,null,null,null,41,null,null,null,null,null,14,18,22,null,null,33,null,null,42,null,null,16,null,21,23,null,34,null,44,null,17,20,null,null,24,null,null,43,null,null,null,null,null,null,25,null,null,null,29,26,null,null,28,27]");
//        TreeNode result = solution.deserialize("[41,37,44,24,39,42,48,1,35,38,40,null,43,46,49,0,2,30,36,null,null,null,null,null,null,45,47,null,null,null,null,null,4,29,32,null,null,null,null,null,null,3,9,26,null,31,34,null,null,7,11,25,27,null,null,33,null,6,8,10,16,null,null,null,28,null,null,5,null,null,null,null,null,15,19,null,null,null,null,12,null,18,20,null,13,17,null,null,22,null,14,null,null,21,23]");
        long endD = System.currentTimeMillis();
        System.out.println("反序列化：\n" + result + ", 耗时[" + (endD - startD) + "ms]");


        long startS = System.currentTimeMillis();
        String serialized = solution.serialize(result);
        long endS = System.currentTimeMillis();
        System.out.println("序列化：\n" + serialized + ", 耗时[" + (endS - startS) + "ms]");
    }

}
